//        https://www.nowcoder.com/practice/491828fc7d93459db450b344c2aaaeef





class Solution
{
public:
    int countPath(vector<vector<int> >& CityMap, int n, int m)
    {
        int x1, x2, y1, y2;
        vector<vector<int>> dp(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (CityMap[i][j] == 1)
                {
                    x1 = i;
                    y1 = j;
                }
                if (CityMap[i][j] == 2)
                {
                    x2 = i;
                    y2 = j;
                }
            }
        }
        int dx = x1 < x2 ? 1 : -1;
        int dy = y1 < y2 ? 1 : -1;
        dp[x1][y1] = 1;
        for (int x = x1 + dx; x != x2 + dx; x += dx)
        {
            dp[x][y1] = CityMap[x][y1] != -1 ? dp[x - dx][y1] : 0;
            if (dp[x - dx][y1] == 0)
                dp[x][y1] = 1;
        }
        for (int y = y1 + dy; y != y2 + dy; y += dy)
        {
            dp[x1][y] = CityMap[x1][y] != -1 ? dp[x1][y - dy] : 0;
            if (dp[x1][y - dy] == 0)
                dp[x1][y] = 1;
        }
        for (int x = x1 + dx; x != x2 + dx; x += dx)
        {
            for (int y = y1 + dy; y != y2 + dy; y += dy)
            {
                dp[x][y] = CityMap[x][y] != -1 ? dp[x - dx][y] + dp[x][y - dy] : 0;
            }
        }

        return dp[x2][y2];
    }
};
